1. Field of the Invention
This invention relates generally to a method for controlling gaps between customers, i.e., customer processes, in service systems with finite buffers and in particular to an apparatus and method for optimal packet dropping to control consecutive packet loss (average packet gap) in a packet buffer.
2. Background of the Related Art
In a packet switched network, data is presented at a transmit end of the network and divided into separate packets of information. These packets are routed through the network and reassembled into the original data at a receive end of the network.
Packet communications are particularly useful in time-shared systems since the user is only using system bandwidth when needed. This allows multiple users the opportunity to be simultaneously connected to the same network since each user only uses system bandwidth when needed. Additionally, because the packet switched system is handling packets rather than directly handling the original information, it is possible to connect a variety of different types of users (e.g. voice, video, and data) to a single network.
Of course there is a limit to the number of packets that the network can handle at one time. If users send too many packets over the system at the same time, congestion can occur. Generally, packet switching nodes throughout the network have buffers (e.g. FIFO buffers) to temporarily store packets. A typical packet switching node may have input buffers for storing incoming packets that are waiting for routing, a switch for routing packets, and output buffers for storing packets that have been routed but are waiting to be sent.
Additionally, source buffers may exist in the user equipment at the transmit end of the network or between the user equipment and the input port to the network. Destination buffers may exist in the user equipment at the receive end of the network or between the user equipment and the output port from the network. Since a great deal of user equipment is bidirectional, source and destination buffers may coexist for some user equipment.
When the packet switched system becomes congested, buffers in the system can become full and are unable to store incoming packets. When this buffer overflow condition occurs, it is necessary to drop packets already in the buffer in order to store incoming packets.
Several different policies for packet dropping in a packet buffer have been developed. One policy is to drop from the rear of the buffer (Rear Dropping, see FIG. 15(a)), i.e. to drop the incoming packets until the buffer is no longer full.
A second policy, suggested by Yin et al. in "Implication of dropping packets from the front of the queue,"IEEE Trans. Commun., vol. 41, 1992, pp. 846-51, is to drop packets from the front of the buffer (Front Dropping, see FIG. 15(b)). Yin et al. shows that a policy of front dropping improves both average buffering delay and the overall loss performance for time constrained traffic.
A third set of policies, one of which is disclosed in U.S. Pat. No. 4,769,810 and 4,769,811, involves marking incoming packets with a priority marker (establishing classes of packets) and dropping low priority packets (Priority Dropping, see FIG. 15(c)). Although this policy decreases the probability of dropping high priority packets, it accomplishes this result at the expense of increasing the probability of dropping low priority packets.
The problem with all of these approaches is that they only control packet loss.